A paging system is a computer system in which the appearance of a large virtual memory is provided through a combination of high speed main memory and slower speed auxiliary memory. The first computer system to use paging was the Atlas machine (Sumner, T. K., One Level Storage System, IEEE Transactions on Computers, April 1962, pp. 223-235).
The original idea of a CPU managed memory hierarchy was introduced by Wilkes (Wilkes, M. V., Slave Memories and Dynamic Storage Allocation, IEEE Transactions on Electronic Computers, pp. 270-271, 1965). The key concept is that a small buffer of frequently referenced data can more quickly respond to fetch requests. Requests that are not in the buffer are fetched from main memory. A small amount of expensive high speed buffer can have a disproportionally good improvement on average access time. The first production computer with cache memory was the IBM 360 Model 85 (Liptay, J. S., Structural aspects of the System/360 Model 85 IIxe2x80x94The Cache, IBM Systems Journal, 7, 1968, pp. 15-21 and Conti, C. J., Concepts for buffer storage, Computer Group News, 2, 1969, pp. 9-13).
Paging systems provide a memory cache of recently used pages and therefore can be considered a specific instance of a caching system. Both caching systems and paging systems require a dynamic mechanism for deciding which data to keep in the buffer. The decision hinges on which page to remove when a new candidate is to be inserted. It is frequently called the replacement algorithm.
The most often used replacement algorithm in computing systems is the Least Recently Used (LRU) algorithm (see Baylis, M. H., Fletcher, D. G., and Howarth, D. J., Paging Studies on the I.C.T. Atlas Computer, Proceedings of the IFIP Congress, pp. 831-837, 1968; Belady, L. A., A Study of Replacement Algorithms for a Virtual-memory Computer, IBM Systems Journal, 5, 1966, pp. 78-100; and U.S. Pat. No. 3,964,028, issued Jun. 15, 1976 to Belady et al.). In many cases the algorithm used is an LRU approximation that will operate with lower overhead. Belady showed that the optimal algorithm would replace the page with the longest time until next reference. However, this is not implementable. In general, replacement algorithms (LRU included) are trying to predict the next reference.
Effelsberg (Effelsberg, W., and Haerder, T., Principles of Database Buffer Management, ACM Transactions on Data Base Systems, 9, 1984, pp. 560-595) analyzed frequency based approaches. The frequency approach was later refined in U.S. Pat. No. 5,043,885, issued Aug. 27, 1991, entitled Data Cache Using Dynamic Frequency Based Replacement and Boundary Criteria, by Robinson). Frequency based algorithms place a higher value on frequently referenced blocks. This is another attempt at ranking blocks by the time of estimated next reference.
These paging and caching techniques have been incorporated into database buffer caches, file system buffer caches, and caches in disk control units. In all cases, LRU variants or frequency based replacement algorithms are used. The systems all share two important characteristics: first, all objects are the same size (or one of a small number of predetermined sizes); second, all blocks take approximately the same time to retrieve from the backing store. In these systems improvements to the replacement algorithm will result in higher hit ratios, lower miss ratios and reduced average latency.
Web page caching introduces two new deviations from previous automatic storage hierarchy systems. First, objects are of a wide range of different sizes. Second, the fetch time in the event of a miss is different (often very different due to network latency, server load and object size). The relaxation that allows variable fetch times and variable size decouples the relationship between hit ratio and average fetch time.
Average user fetch time is a reasonable objective function for the optimization problem for which the replacement algorithm is used. If objects are variable in size, then the fast buffer may be more effectively used for multiple small objects instead of one large object that is referenced more often than any one of the small objects. Long network latency to a particular object may make it a better candidate to retain in memory than other objects that are referenced more frequently but have lower miss penalties.
One proposed solution is a server centric system in which the server gives hints to clients about what to cache (see Using the Overhead Costs of Network Messages to Choose Between Cache Coherency Strategies in a Distributed File System, IBM Technical Disclosure Bulletin (TDB), pp. 266-268, (August 1991)). Here, the server decides whether to cache an item. The concern is the tradeoff, in network traffic, of invalidate messages versus more data movement when caching is not done. The TDB article does not make any proposal about which cacheable items should actually be cached. The TDB article makes use of a cost function (which are pervasive in optimizations) for making decisions.
The Hybrid algorithm uses a cost function that includes: time to connect to a server; bandwidth to the server; the number of times requested; and the size (see Wooster, R., and Abrams, M. Proxy Caching That Estimates Page Load Delays, 6th International World Wide Web Conference, Apr. 7-11, 1997, Santa Clara, Calif.). It also includes a number of tuning parameters that must be experimentally determined. The cost function should really be viewed as a heuristic because it is not dimensionally meaningfull (time is added to time divided by size). It does not use reference probabilities for evaluating a cost function.
The current state of the art is recognizing that size, retrieval time, and frequency of reference may play a role in replacement algorithms. However, at this time, it is only entering in empirically created decision functions. Thus, the need remains for an improved method and system for evaluating the relative value of cacheable objects. The need also remains for a method and system that makes use of reference probabilities in evaluating replacement costs. The present invention addresses these needs.
In accordance with the aforementioned needs, the present invention is directed to a computerized method, system and program storage device for managing an object store, such as a cache, based on a replacement penalty.
An example of a method having features of the present invention includes the the steps of: collecting one or more performance statistics about one or more storage repositories from which one or more objects can be retrieved; retrieving an object from a storage repository, in response to an object reference; determining a reference probability for an object; determining and associating a replacement penalty with the object wherein the replacement penalty is based on the one or more performance statistics and the reference probability; and storing the object and an associated replacement penalty for the object. The storage repositories include but are not limited to locally attached devices, network sites, and/or remotely attached devices.
The replacement penalty of the present invention can be used to free storage, for example, by reducing the storage used by stored objects or replacing stored objects. An example of a method for reducing the storage used by stored objects includes the additional steps of: receiving a new object reference to a new object, not in the object store; retrieving an object from a storage repository, in response to an object reference; determining there is insufficient free space in the object store for the new object; and reducing the resolution of one or more objects in the object store until sufficient space is available to store the new object; and storing the new object and an associated replacement penalty for the new object.
An example of a method for cache replacement according to the present invention includes the steps of: collecting one or more performance statistics about one or more storage repositories from which one or more objects can be retrieved; estimating a reference probability for the one or more objects; receiving an object reference to an object not in the object store; retrieving an object from a storage repository, in response to receiving the object reference; determining there is insufficient free space in the object store for the new object; and replacing one or more objects in the object store, the sum of the sizes of which is equal to or greater than the size of the new object, with the new object based on the associated replacement penalty of the one or more cached objects; wherein the replacement penalty is based on the one or more performance statistics and the reference probability.
The present invention also has features for prioritizing the objects based on the associated replacement penalty of the one or more cached objects; and replacing the one or more cached objects having a minimum associated replacement penalty priority.
The present invention has other features for determining a reference probability, including the steps of: associating and maintaining a least recently used (LRU) list of records corresponding to objects in the object store; partitioning the LRU list into a number of sections; inserting a record associated with a most recently referenced object at a head of the LRU list, in response to said storing step; and maintaining object reference probability statistics for a set of objects in each section of the LRU.
The present invention also has features wherein maintaining the object reference probability statistics further includes the steps of: incrementing a reference count N(i) for a section i if an object currently in said section i is referenced; wherein the probability (P) that an object in said section i will be referenced is: P (reference to object in section i)=N(i)/(O(i)xc3x97T), wherein O(i) represents the number of objects in said section i, and T represents a total number of references for all sections. The replacement penalty can be recalculated each time a change is made to the set of objects in any section of the LRU, based on the reference probability specific to that section.
The replacement penalty (R) determination is preferably based on the reference probability (P) for the object and performance and/or usage statistics. An example of the performance statistics includes: an availability of the object (A); a size of the object (S); a latency associated with retrieving the object from a storage repository (L); or a bandwidth of the path to the storage repository (B).
An example of the usage statistics includes statistics on time delays (D) associated with abort requests. For example, in a system including a browser for retrieving objects via the Internet, the replacement penalty could factor in an annoyance function for a specific requester or set of requesters by instrumenting the browser STOP (also called Abort) function and analyzing time interval statistics associated with usage of the STOP function.